// Copyright Google Inc. All Rights Reserved.
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//     http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS-IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
//

#ifndef S2_S2FRACTAL_H_
#define S2_S2FRACTAL_H_

#include <cmath>
#include <memory>
#include <random>
#include <vector>

#include "absl/synchronization/mutex.h"
#include "s2/r2.h"
#include "s2/s2loop.h"

// A simple class that generates "Koch snowflake" fractals (see Wikipedia for an
// introduction).  There is an option to control the fractal dimension (between
// 1.0 and 2.0); values between 1.02 and 1.50 are reasonable simulations of
// various coastlines.  The default dimension (about 1.26) corresponds to the
// standard Koch snowflake.  (The west coast of Britain has a fractal dimension
// of approximately 1.25.)
//
// The fractal is obtained by starting with an equilateral triangle and
// recursively subdividing each edge into four segments of equal length.
// Therefore the shape at level "n" consists of 3*(4**n) edges.  Multi-level
// fractals are also supported: if you set min_level() to a non-negative value,
// then the recursive subdivision has an equal probability of stopping at any of
// the levels between the given min and max (inclusive).  This yields a fractal
// where the perimeter of the original triangle is approximately equally divided
// between fractals at the various possible levels.  If there are k distinct
// levels {min,..,max}, the expected number of edges at each level "i" is
// approximately 3*(4**i)/k.
class S2Fractal {
 public:
  // You must call set_max_level() or SetLevelForApproxMaxEdges() before
  // calling MakeLoop().
  S2Fractal();

  // Set the maximum subdivision level for the fractal (see above).
  // REQUIRES: max_level >= 0
  void set_max_level(int max_level);
  int max_level() const { return max_level_; }

  // Set the minimum subdivision level for the fractal (see above).  The
  // default value of -1 causes the min and max levels to be the same.  A
  // min_level of 0 should be avoided since this creates a significant chance
  // that none of the three original edges will be subdivided at all.
  //
  // DEFAULT: max_level()
  void set_min_level(int min_level_arg);
  int min_level() const { return min_level_arg_; }

  // Set the min and/or max level to produce approximately the given number
  // of edges.  (The values are rounded to a nearby value of 3*(4**n).)
  void SetLevelForApproxMinEdges(int min_edges);
  void SetLevelForApproxMaxEdges(int max_edges);

  // Set the fractal dimension.  The default value of approximately 1.26
  // corresponds to the stardard Koch curve.  The value must lie in the range
  // [1.0, 2.0).
  //
  // DEFAULT: log(4) / log(3) ~= 1.26
  void set_fractal_dimension(double dimension);
  double fractal_dimension() const { return dimension_; }

  // Return a lower bound on ratio (Rmin / R), where "R" is the radius
  // passed to MakeLoop() and "Rmin" is the minimum distance from the
  // fractal boundary to its center, where all distances are measured in the
  // tangent plane at the fractal's center.  This can be used to inscribe
  // another geometric figure within the fractal without intersection.
  double min_radius_factor() const;

  // Return the ratio (Rmax / R), where "R" is the radius passed to
  // MakeLoop() and "Rmax" is the maximum distance from the fractal boundary
  // to its center, where all distances are measured in the tangent plane at
  // the fractal's center.  This can be used to inscribe the fractal within
  // some other geometric figure without intersection.
  double max_radius_factor() const;

  // Return a fractal loop centered around the z-axis of the given
  // coordinate frame, with the first vertex in the direction of the
  // positive x-axis.  In order to avoid self-intersections, the fractal is
  // generated by first drawing it in a 2D tangent plane to the unit sphere
  // (touching at the fractal's center point) and then projecting the edges
  // onto the sphere.  This has the side effect of shrinking the fractal
  // slightly compared to its nominal radius.
  std::unique_ptr<S2Loop> MakeLoop(const Matrix3x3_d& frame,
                                   S1Angle nominal_radius) const;

 private:
  void ComputeMinLevel();
  void ComputeOffsets();
  void GetR2Vertices(std::vector<R2Point>* vertices) const;
  void GetR2VerticesHelper(const R2Point& v0, const R2Point& v4, int level,
                           std::vector<R2Point>* vertices) const;

  // Reset the PRNG to the default seed.
  void Reseed() const {
    absl::WriterMutexLock lock(&lock_);
    random_.seed();
  }

  bool OneIn(int32 n) const {
    absl::WriterMutexLock lock(&lock_);
    return std::uniform_int_distribution<int>(0, n - 1)(random_) == 0;
  }

  // Mutable source of randomness and a lock to synchronize it.
  mutable std::default_random_engine random_;
  mutable absl::Mutex lock_;

  int max_level_ = -1;
  int min_level_arg_ = -1;  // Value set by user
  int min_level_ = -1;      // Actual min level (depends on max_level_)
  double dimension_ = std::log(4) / std::log(3);  // Standard Koch curve

  // The ratio of the sub-edge length to the original edge length at each
  // subdivision step.
  double edge_fraction_ = 0;

  // The distance from the original edge to the middle vertex at each
  // subdivision step, as a fraction of the original edge length.
  double offset_fraction_ = 0;

  S2Fractal(const S2Fractal&) = delete;
  void operator=(const S2Fractal&) = delete;
};

#endif  // S2_S2FRACTAL_H_
